package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/**
 *
 * 题型：二叉树的后序遍历，求最大深度
 *
 * 865. 具有所有最深节点的最小子树   https://leetcode.cn/problems/smallest-subtree-with-all-the-deepest-nodes/description
 * 1123. 最深叶节点的最近公共祖先  https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/description/
 * 重复
 *
 *
 * ```
 * 865. 具有所有最深节点的最小子树
 * 给定一个根为 root 的二叉树，每个节点的深度是 该节点到根的最短距离 。
 * 返回包含原始树中所有 最深节点 的 最小子树 。
 * 如果一个节点在 整个树 的任意节点之间具有最大的深度，则该节点是 最深的 。
 * 一个节点的 子树 是该节点加上它的所有后代的集合。
 *
 *
 * 示例 1：
 * 输入：root = [3,5,1,6,2,0,8,null,null,7,4]
 * 输出：[2,7,4]
 * 解释：
 * 我们返回值为 2 的节点，在图中用黄色标记。
 * 在图中用蓝色标记的是树的最深的节点。
 * 注意，节点 5、3 和 2 包含树中最深的节点，但节点 2 的子树最小，因此我们返回它。
 *
 * 示例 2：
 * 输入：root = [1]
 * 输出：[1]
 * 解释：根节点是树中最深的节点。
 *
 * 示例 3：
 * 输入：root = [0,1,3,null,2]
 * 输出：[2]
 * 解释：树中最深的节点为 2 ，有效子树为节点 2、1 和 0 的子树，但节点 2 的子树最小。
 *
 * 提示：
 * 树中节点的数量在 [1, 500] 范围内。
 * 0 <= Node.val <= 500
 * 每个节点的值都是 独一无二 的。
 * ```
 */
class leetcode_1123 {
    @Test
    fun test_1() {
        val root: TreeNode = TreeNode(3)
        val n0 = TreeNode(0)
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val n7 = TreeNode(7)
        val n8 = TreeNode(8)
        root.left = n5
        root.right = n1

        n5.left = n6
        n5.right = n2

        n2.left = n7
        n2.right = n4

        n1.left = n0
        n1.right = n8

        val actual = subtreeWithAllDeepest(root)
        val expect = n2
        Assert.assertTrue(expect == actual)
    }

    @Test
    fun test_2() {
        val root: TreeNode = TreeNode(1)
        val actual = subtreeWithAllDeepest(root)
        val expect = root
        Assert.assertTrue(expect == actual)
    }

    @Test
    fun test_3() {
        // 0,1,3,null,2
        val n0 = TreeNode(0)
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val root: TreeNode = n0
        n0.left = n1
        n0.right = n3

        n1.right = n2

        val actual = subtreeWithAllDeepest(root)
        val expect = n2
        Assert.assertTrue(expect == actual)
    }

    private fun subtreeWithAllDeepest(root: TreeNode?): TreeNode? {
        /**
         * 题型：二叉树的后序遍历，求最大深度
         * 思路：求先求左右子树的最大深度以及节点，再向上汇总
         * https://leetcode.cn/problems/smallest-subtree-with-all-the-deepest-nodes/solutions/18767/ju-you-suo-you-zui-shen-jie-dian-de-zui-xiao-zi-sh
         */
        return f(root, 1).root
    }

    private fun f(root: TreeNode?, depth: Int): Result {
        // 1 确定函数参数以及返回值
        // 返回值：最深节点，以及它的深度

        // 2 确定终止条件
        if (null == root) {
            return Result(null, 0)
        }

        // 3 确定单层递归的逻辑：后序遍历
        // 左
        val left: Result = f(root.left, depth + 1)

        // 右
        val right: Result = f(root.right, depth + 1)

        // 中
        if (left.depth > right.depth) {
            return Result(left.root, left.depth + 1)
        } else if (left.depth == right.depth) {
            return Result(root, left.depth + 1)
        } else {
            return Result(right.root, right.depth + 1)
        }
    }

    data class Result(val root: TreeNode?, val depth: Int)
}